/*
实验8-3 打怪升级
分数 30
作者 陈越
单位 浙江大学

dgsj.JPG

很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。

你的任务有两件：

        帮助玩家确定一个最合算的空降位置，即空降到地图中的某个堡垒，使得玩家从这个空降点出发，到攻下最难攻克（即耗费能量最多）的那个堡垒所需要的能量最小；
        从这个空降点出发，帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一，则选择沿途缴获武器总价值最高的解，题目保证这种解是唯一的。

输入格式:

输入第一行给出两个正整数 N (≤1000) 和 M，其中 N 是堡垒总数，M 是怪兽总数。为简单起见，我们将堡垒从 1 到 N 编号。随后 M 行，第 i 行给出了第 i 只怪兽的信息，格式如下：

B1 B2 怪兽能量 武器价值

其中 B1 和 B2 是怪兽把守的道路两端的堡垒编号。题目保证每对堡垒之间只有一只怪兽把守，并且 怪兽能量 和 武器价值 都是不超过 100 的正整数。

再后面是一个正整数 K（≤N）和玩家想要攻克的 K 个目标堡垒的编号。
输出格式:

首先在一行中输出玩家空降的堡垒编号 B0。如果有多种可能，则输出编号最小的那个。

随后依次为玩家想要攻克的每个堡垒 B 推荐最省能量的攻克路径，并列出需要耗费的能量值和沿途缴获武器的总价值。注意如果最省力的路径不唯一，则选择沿途缴获武器总价值最高的解。格式为：

B0->途经堡垒1->...->B
总耗费能量 武器总价值

输入样例:

6 12
1 2 10 5
2 3 16 20
3 1 4 2
2 4 20 22
4 5 2 2
5 3 12 6
4 6 8 5
6 5 10 5
6 1 20 25
1 5 8 5
2 5 2 1
2 6 8 5
4
2 3 6 5

输出样例:

5
5->2
2 1
5->1->3
12 7
5->4->6
10 7
5
0 0
*/

#include "../base/MGraph-floyed.cpp"

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

#define MaxWeigth 0x7FFF

// 定义权重结构体
struct Weight {
    int energy; // 怪兽的能量
    int value;  // 武器的价值

    Weight(int e = 0, int v = 0) : energy(e), value(v) {}

    bool operator==(const Weight& other) {
        return energy == other.energy && value == other.value;
    }

    bool operator!=(const Weight& other) {
        return energy != other.energy || value != other.value;
    }
    // 重载加法运算符
    Weight operator+(const Weight& other) const {
        return Weight(energy + other.energy, value + other.value);
    }

    // 重载比较运算符
    bool operator>(const Weight& other) const {
        if (energy == other.energy) return value < other.value;
        return energy > other.energy;
    }

    // 重载比较运算符
    bool operator<(const Weight& other) const {
        if (energy == other.energy) return value > other.value;
        return energy < other.energy;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    MGraph<int, Weight> graph(n, Weight(MaxWeigth, 0), false);

    for (int i = 0; i < m; ++i) {
        int b1, b2, energy, value;
        cin >> b1 >> b2 >> energy >> value;
        graph.add_edge(b1, b2, Weight(energy, value));
    }

    // 计算从每个堡垒出发到其他堡垒的最大能量消耗，选择最大能量消耗最小的堡垒作为空降点。
    // 计算每个堡垒的最大能量消耗
    Weight **weight = init2DArray<Weight>(n + 1);
    int **path = init2DArray<int>(n + 1);
    floyed(graph, weight, path);

    vector<int> max_energy(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (weight[i][j].energy > max_energy[i]) {
                max_energy[i] = weight[i][j].energy;
            }
        }
    }

    // 找到最佳空降点
    int best_start_node = min_element(max_energy.begin() + 1, max_energy.end()) - max_energy.begin();
    cout << best_start_node << endl;

    // 处理目标堡垒
    int k;
    cin >> k;
    vector<int> targets(k);
    for (int i = 0; i < k; ++i) {
        cin >> targets[i];
    }

    for (int target : targets) {
        int current = target;
        vector<int> current_path;
        while (current != best_start_node) {
            current_path.push_back(current);
            current = path[best_start_node][current];
        }
        cout << best_start_node;
        reverse(current_path.begin(), current_path.end());
        for (int p : current_path) {
            cout << "->" << p;
        }
        cout << endl;
        cout << weight[best_start_node][target].energy << " " << weight[best_start_node][target].value << endl;
    }
    free2DArray<Weight>(weight, n + 1);
    free2DArray<int>(path, n + 1);

    return 0;
}